package com.leecode;

import java.util.HashMap;
import java.util.Map;

/**
 * 70. 爬楼梯
 *
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 注意：给定 n 是一个正整数。
 */
public class Leet70 {
	public static void main(String[] args) {
		System.out.println(new Leet70().climbStairs(4));
	}

	/**
	 * 这是我初学,还不会dp的时候,悟出来的"记录法"
	 */
	Map<Integer,Integer> map=new HashMap();
	public int climbStairs(int n) {
		if(n==1 )return 1;
		if(n==2)return 2;

		int a=0;
		int b=0;
		/**
		 *	引入map,注意map的api是containsKey,n越来越大时,f(n)=f(n-2)+f(n-1),f(n-2)已经计算过了,f(n-1)又要再算一次f(n-2)
		 * leet解法:数组index从0加1,1加2,2加3,一直迭代累加也很秀!!!
		 */
		if(this.map.containsKey(n-2)){
			a=this.map.get(n-2);
		}else{
			a=climbStairs(n-2);
			this.map.put(n-2,a);
		}
		if(this.map.containsKey(n-1)){
			b=this.map.get(n-1);
		}else{
			b=climbStairs(n-1);
			this.map.put(n-1,b);
		}
		return a+b;
	}

	/**
	 * 100%,97%,斐波那契数列（Fibonacci sequence）
	 */
	public int climbStairs2(int n) {
		if(n==1)return 1;
		if(n==2)return 2;

		int pre=1;
		int aft=2;
		int temp=0;
		for(int a=3;a<=n;a++){
			temp=pre+aft;
			pre=aft;
			aft=temp;
		}

		return temp;
	}
}
